#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * 单调站
 *84. 柱状图中最大的矩形
困难
2.3K
相关企业
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
 *
 *这玩意是单调站的问题 单调站就是寻找一个数值的大于他的第一个数或者小于他的第一个数
 * */
int largestRectangleArea(vector<int> &heights) {

    //
    heights.push_back(-1);//存一个没用的否则容易卡用力
    stack<int> st;//这里我存储下标了
    int maxV = 0;
    //int stackMin=INT_MAX;
    for (int i = 0; i < heights.size(); ++i) {
        if (st.empty()) {
            st.push(i);
        } else {
            //注意 栈里面数据应该是单调增函数  卧槽这个为什么是增函数得想想啊
            while (!st.empty() && heights[i] < heights[st.top()]) {
                // 第一次i求1对应高对应的面积
                int height = heights[st.top()];
                st.pop();
                int left = 0;
                int right = i;
                if (st.size() == 0) {
                    maxV = max(maxV, (right - left) * height);
                } else {
                    left = st.top();
                    maxV = max(maxV, (right - left - 1) * height);
                }


            }
            st.push(i);


        }

    }

    int size = 0;
    int h = 0;
    while (!st.empty()) {
        if (heights[st.top()] != 0) {
            h = heights[st.top()];
            size++;
        }

        st.pop();
    }

    if (size > 0) {
        maxV = max(maxV, (h * size));
    }

    return maxV;
}